<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8">
		<title>二叉搜索封装</title>
	</head>
	<body>
	</body>
</html>
<script type="text/javascript">
	/*
	二叉搜索树常见操作
		insert(key):向树中插入一个新的键
		search(key):在树种查找一个键，如果节点存在，则返回true;如果不存在，则返回false
		preOrderTraverse:通过先序遍历方式遍历所有节点。
		inOrderTraverse:通过中序遍历方式遍历所有节点。
		postOrderTraverse:通过后序遍历方式遍历所有节点。
		min:返回树种最小的值/键。
		max：返回树种最大的值/键。
		remove(key)：从树种移除某个键。
	*/



	// 二叉搜索树
	function BinarySearchTree() {
		function Node(key) {
			this.key = key
			this.left = null
			this.right = null
		}

		// 属性
		this.root = null

		// 方法
		// 插入
		BinarySearchTree.prototype.insert = function(key) {
			// 1.首先根据key创建节点
			var newNode = new Node(key)

			// 2.判断根节点是否有值
			if (this.root == null) {
				this.root = newNode
			} else {
				this.insertNode(this.root, newNode)
			}
		}
		// 插入递归（内部方法）
		BinarySearchTree.prototype.insertNode = function(node, newNode) {
			if (newNode.key < node.key) { //向左查找
				if (node.left == null) {
					node.left = newNode
				} else {
					this.insertNode(node.left, newNode)
				}
			} else { //向右查找
				if (node.right == null) {
					node.right = newNode
				} else {
					this.insertNode(node.right, newNode)
				}
			}
		}

		// 树的遍历
		// 1.先序遍历
		BinarySearchTree.prototype.preOrderTraversal = function(handler) {
			this.preOrderTraversalNode(this.root, handler)
		}
		BinarySearchTree.prototype.preOrderTraversalNode = function(node, handler) {
			if (node != null) {
				// 查找经过的节点
				handler(node.key)
				// 左子节点
				this.preOrderTraversalNode(node.left, handler)
				// 查找右子节点
				this.preOrderTraversalNode(node.right, handler)
			} 
		}
		// 12.中序遍历
		BinarySearchTree.prototype.inOrderTraversal = function(handler) {
			this.inOrderTraversalNode(this.root, handler)
		}
		BinarySearchTree.prototype.inOrderTraversalNode = function(node, handler) {
			if (node != null) {
				// 查找左子树
				this.inOrderTraversalNode(node.left, handler)
				handler(node.key)
				// 查找右子树
				this.inOrderTraversalNode(node.right, handler)
			}
		}
		// 3.后序遍历 postOrderTraverse
		BinarySearchTree.prototype.postOrderTraversal = function(handler) {
			this.postOrderTraversalNode(this.root, handler)
		}
		BinarySearchTree.prototype.postOrderTraversalNode = function(node, handler) {
			if (node != null) {
				// 查找左子树
				this.postOrderTraversalNode(node.left, handler)
				// 查找右子树
				this.postOrderTraversalNode(node.right, handler)
				handler(node.key)
			}
		}
		// 最小值
		BinarySearchTree.prototype.min = function() {
			var node = this.root
			var key = null
			while (node != null) {
				key = node.key
				node = node.left
			}
			return key
		}
		// 最大值
		BinarySearchTree.prototype.max = function() {
			var node = this.root
			var key = null
			while (node != null) {
				key = node.key
				node = node.right
			}
			return key
		}

		// 搜索特定的值
		BinarySearchTree.prototype.search = function(key) {
			return this.searchNode(this.root, key)
		}
		BinarySearchTree.prototype.searchNode = function(node, key) {
			if (node === null) {
				return false
			}
			// 判断传入的key跟Node节点的值的大小
			if (node.key > key) { //传入的key较小
				return this.searchNode(node.left, key)
			} else if (node.key < key) { //传入的key较大
				return this.searchNode(node.right, key)
			} else {
				return true
			}
		}
		BinarySearchTree.prototype.searchWhile = function(key) {
			// 1.获取根节点
			var node = this.root
			while (node != null) {
				if (node.key > key) {
					node = node.left
				} else if (node.key < key) {
					node = node.right
				} else {
					return true
				}
			}

			return false
		}

		// 删除节点
		BinarySearchTree.prototype.remove = function(key) {
			// 1.寻找要删除的节点
			// 1.1定义变量，保存信息
			var current = this.root;
			var parrent = null;
			var isLeftChild = true;
			// 1.2查找循环删除的节点
			while (current.key != key) {
				parrent = current
				if (current.key > key) {
					current = current.left
					isLeftChild = true
				} else if (current.key < key) {
					current = current.right
					isLeftChild = false
				}
				// 某种情况：已经找到了最后的节点依然没有找到相等的key
				if (current == null) return false
			}

			// 2.根据对应的情况删除节点
			// current.key == key
			// 2.1删除的节点是叶子节点（没有子节点）
			if (current.left == null && current.right == null) {
				if (current == this.root) {
					this.root = null
				} else if (isLeftChild) {
					current.left = null
				} else {
					current.right = null
				}
			} else if (current.right == null) { // 2.2删除的节点有一个子节点

				if (current == this.root) {
					this.root = current.left
				} else if (isLeftChild) {
					parent.left = current.left
				} else {
					parent.right = current.left
				}
			} else if (current.left == null) {
				if (current == this.root) {
					this.root = current.right
				} else if (isLeftChild) {
					parent.left = current.right
				} else {
					parent.right = current.right
				}
			} else { // 2.3删除的节点有两个子节点
				var successor = this.getSuccessor(current)
				if(current== this.root){
					this.root = successor
				}else if(isLeftChild){
					parrent.left=successor
				}else{
					parrent.right=successor
				}
				// 3.将删除节点的左子树 = current.left
				successor.left = current.left
			}
			// return true
		}
		// 找后继的方法
		BinarySearchTree.prototype.getSuccessor = function(delNode){
			// 1.定义变量，保存找到的后继
			var  successor = delNode
			var current = delNode.right
			var successorParent =delNode
			
			// 2.循环查找
			while(current !=null){
				successorParent = successor
				successor=current
				current=current.left
			}
			
			// 3.判断寻找的后继节点是否直接就是delNode的right节点
			if(successor !=delNode.right){
				successorParent.left=successor.right
				successor.right=delNode.right
			}
			return successor
			
		}
		// 删除递归
		
		BinarySearchTree.prototype.removeTx = function(key) {
			this.root = this.removeNode(this.root, key)
			console.log('this.root',this.root)
		}
		BinarySearchTree.prototype.removeNode = function(node, key) {
			if (node == null) {
				return null;
			}
			if (key == node.key) {
				//如果没有子节点
				if (node.right == null && node.left == null) {
					return null; //直接将节点设为空
				}
				//如果没有左子节点
				if (node.left == null) {
					return node.right; //直接指向其右节点
				}
				//如果没有右子节点
				if (node.right == null) {
					return node.left;
				}
				//如果有两个节点
				if (node.right != null && node.left != null) {
					var tempNode = this.getSmallest(node.right); //找到最小的右节点
					node.key = tempNode.key;
					node.right = this.removeNode(node.right, tempNode.key); //依次寻找
					return node;
				}
			} else if (key < node.key) {
				node.left = this.removeNode(node.left, key);
				return node;
			} else {
				node.right = this.removeNode(node.right, key);
				return node;
			}
		}
		BinarySearchTree.prototype.getSmallest = function(node) {
			// 查找最小的节点
			if (node.left == null) {
				return node;
			} else {
				return this.getSmallest(node.left);
			}
		}
	}


	// 测试

	var bst = new BinarySearchTree();

	// 1.插入数据
	bst.insert(11)
	bst.insert(7)
	// bst.insert(15)
	// bst.insert(5)
	// bst.insert(3)
	// bst.insert(9)
	// bst.insert(8)
	// bst.insert(10)
	// bst.insert(13)
	// bst.insert(12)
	// bst.insert(14)
	// bst.insert(20)
	// bst.insert(18)
	// bst.insert(25)
	// bst.insert(6)
	// bst.insert(19)
	// bst.insert(22)
	// bst.insert(21)
	// 2.测试遍历
	// 先序遍历
	// var resuletString=""
	// bst.preOrderTraversal(function(key){
	// 	resuletString+=key+" "
	// })
	// alert(resuletString)

	// // 中序遍历
	// var inOrderString=""
	// bst.inOrderTraversal(function(key){
	// 	inOrderString+=key+" "
	// })
	// alert(inOrderString)

	// // 后序遍历
	// var postOrderString=""
	// bst.postOrderTraversal(function(key){
	// 	postOrderString+=key+" "
	// })
	// alert(postOrderString)

	// // 最值
	// console.log(bst.min())
	// console.log(bst.max())

	// // 搜索
	// console.log(bst.search(36))
	// console.log(bst.searchWhile(36))
	// console.log(bst.search(6))
	// console.log(bst.searchWhile(6))


	// 删除
	bst.removeTx(11)
	// var removeString = ""
	// bst.postOrderTraversal(function(key) {
	// 	removeString += key + " "
	// })
	// alert(removeString)
</script>
